package org.example.study;

import java.math.BigInteger;
import java.util.*;

/**
 * @Author chaigq
 * @Date 2020/10/11 4:12 下午
 * @Version 1.0
 */
public class studyJzOffer {

    /**
     * 1、组中重复的数字
     * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
     * 返回：重复的数字
     * 思路：
     * 解题一：使用set集合，set 集合不允许重复数据
     */
    public int findRepeatNumber(int[] nums) {

        Set<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            if (set.contains(num)) {
                return num;
            }
            set.add(num);
        }
        return -1;
    }

    /**
     * 2、二维数组中的查找
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     * <p>
     * 思路：
     * 从右上角进行比较
     */
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        // 行 和 列
        int rows = matrix.length;
        int cloums = matrix[0].length;
        int row = 0;
        int cloum = cloums - 1;
        while (row < rows && cloum >= 0) {
            if (target == matrix[row][cloum]) {
                return true;
            } else if (target > matrix[row][cloum]) {
                // 大于右上
                row++;
            } else {
                // 小于右上
                cloum--;
            }
        }
        return false;
    }

    /**
     * 3、替换空格
     * 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
     */
    public String replaceSpace(String s) {

        return s.replace(" ", "%20");
    }

    /**
     * 4、从头到尾打印链表
     * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
     */
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public int[] reversePrint(ListNode head) {

        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    /**
     * 5、重建二叉树
     * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
     * <p>
     * 思路：
     * 前序  、中序、后序遍历的规则
     * 前序：先根节点，再左子树，最后右子树
     * 中序：先左子树，再根节点，最后右子树
     * 后序：先左子树，再右子树，最后根节点
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 重建二叉树结构
        int n = preorder.length;
        if (n == 0) {
            return null;
        }
        int index = 0;
        TreeNode rootTree = new TreeNode(preorder[0]);
        // 遍历后序数组
        for (int i = 0; i < n; i++) {
            if (inorder[i] == preorder[0]) {
                // 找到左右子树分界点
                index = i;
                // 将左子树和右子树分开
                break;
            }
        }
        // Arrays.copyOfRange(T[ ] original,int from,int to)
        //将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。
        //注意这里包括下标from，不包括上标to。
        rootTree.left = buildTree(Arrays.copyOfRange(preorder, 1, 1 + index), Arrays.copyOfRange(inorder, 0, index));
        rootTree.right = buildTree(Arrays.copyOfRange(preorder, 1 + index, n), Arrays.copyOfRange(inorder, index + 1, n));
        return rootTree;
    }

    /**
     * 6、用两个栈实现队列
     * 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
     * <p>
     * 示例：
     * 输入：
     * ["CQueue","appendTail","deleteHead","deleteHead"] === 表示操作步骤
     * <p>
     * [[],[3],[],[]]
     * 输出：[null,null,3,-1]
     * <p>
     * [[],[3],[],[]]
     * 这个表示每一行代码操作所需要的参数
     * <p>
     * 举例：
     * CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。
     * appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。
     * deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
     * deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
     * <p>
     * 以上的输入其实是一个代码执行的步骤描述与其对应所需参数。
     * <p>
     * 即两个纬度：
     * 1、操作描述
     * 2、此次操作所需参数
     * 3、操作描述与操作所需参数是通过默认顺序一一对应的。
     */
    class CQueue {
        // 定义两个队列
        LinkedList<Integer> stack1;
        LinkedList<Integer> stack2;

        // 初始化新队列
        public CQueue() {
            stack1 = new LinkedList<>();
            stack2 = new LinkedList<>();
        }

        // 队列尾部插入整数
        public void appendTail(int value) {
            stack1.add(value);
        }

        // 出队列
        public int deleteHead() {
            if (stack2.isEmpty()) {
                // 当队列为空，返回-1
                if (stack1.isEmpty()) {
                    return -1;
                }
                // 当栈1不为空时
                while (!stack1.isEmpty()) {
                    // stack1 出栈。stack2 入栈
                    stack2.add(stack1.pop());
                }
                return stack2.pop();
            } else {
                return stack2.pop();
            }
        }
    }

    /**
     * 7、10- I. 斐波那契数列
     * 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
     * <p>
     * F(0) = 0,   F(1) = 1
     * F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
     * 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 2
     * 输出：1
     */
    public int fib(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            int sum = 0;
            int a = 0;
            int b = 1;
            for (int i = 2; i <= n; i++) {
                sum = (a + b) % 1000000007;
                a = b;
                b = sum;
            }
            return sum;
        }
    }

    /**
     * 7、10- II. 青蛙跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     * <p>
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * <p>
     * 示例 1：
     * 输入：n = 2
     * 输出：2
     */
    public int numWays(int n) {

        if (n < 2) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else {
            int result = 0;
            int a = 1;
            int b = 2;
            for (int i = 3; i <= n; i++) {
                result = (a + b) % 1000000007;
                a = b;
                b = result;
            }
            return result;
        }
    }

    /**
     * 8、旋转数组的最小数字
     * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
     * 例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
     */
    public int minArray(int[] numbers) {

        int min = numbers[0];
        for (int num : numbers) {
            min = Math.min(min, num);
        }
        return min;

    }

    /**
     * 剑指 Offer 12. 矩阵中的路径
     * 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，
     * 每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。
     * 例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
     * <p>
     * [["a","b","c","e"],
     * ["s","f","c","s"],
     * ["a","d","e","e"]]
     * <p>
     * 但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
     */
    public boolean exist(char[][] board, String word) {
        // 假如参数不满足条件，将直接返回
        if (board == null || board[0] == null || board.length == 0 || board[0].length == 0 || word == null || word.equals("")) {
            return false;
        }
        boolean bool = false;
        // board为char类型数组，所以将字符串转换成char类型数组
        char[] words = word.toCharArray();
        // 遍历矩阵集合
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // 调用判断方法
                if (existBool(i, j, board, words, 0)) {
                    return true;
                }
                ;
            }
        }
        return bool;
    }

    public boolean existBool(int i, int j, char[][] board, char[] words, int start) {

        // 不满足条件判断
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != words[start]) {
            return false;
        }
        if (start == words.length - 1) {
            return true;
        }
        char temp = board[i][j];
        board[i][j] = '/';
        // 根据上下左右进行查找,只要有一个方向返回true就行
        boolean bool = existBool(i - 1, j, board, words, start + 1) || existBool(i + 1, j, board, words, start + 1) ||
                existBool(i, j - 1, board, words, start + 1) || existBool(i, j + 1, board, words, start + 1);
        board[i][j] = temp;
        return bool;
    }

    /**
     * 剑指 Offer 13. 机器人的运动范围
     * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
     * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
     * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
     * <p>
     * 示例 1：
     * 输入：m = 2, n = 3, k = 1
     * 输出：3
     * <p>
     * 示例 2：
     * 输入：m = 3, n = 1, k = 0
     * 输出：1
     * <p>
     * 条件：
     * 1 <= n,m <= 100
     * 0 <= k <= 20
     */
    public int movingCount(int m, int n, int k) {
        if (m <= 0 || n <= 0) {
            return 0;
        }
        boolean[][] booleans = new boolean[m][n];
        return moveGet(0, 0, m, n, k, booleans);
    }

    public int moveGet(int startm, int startn, int m, int n, int k, boolean[][] booleans) {
        if (startm < 0 || startm >= m || startn < 0 || startn >= n || getX(startm) + getX(startn) > k || booleans[startm][startn]) {
            return 0;
        }
        booleans[startm][startn] = true;
        // 向下和向右,第一次需要加上
        return 1 + moveGet(startm, startn + 1, m, n, k, booleans) + moveGet(startm + 1, startn, m, n, k, booleans);
    }

    public int getX(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }

    /**
     * 剑指 Offer 14- I. 剪绳子
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。
     * 请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
     * <p>
     * 示例 1：
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1
     * <p>
     * 示例 2:
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     * <p>
     * 提示：
     * 2 <= n <= 58
     */
    public int cuttingRope(int n) {
        if (n == 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        for (int i = 5; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                // 拆分有4中情况
                int a = j * dp[i - j];  // j不拆，i-j 能拆
                int b = j * (i - j);  // j不拆，i-j 不拆
                int c = dp[j] * (i - j);    // j拆，(i-j)不拆
                int d = dp[j] * dp[i - j];   // j拆，i-j 能拆
                dp[i] = Math.max(dp[i], Math.max(Math.max(a, b), Math.max(c, d)));
            }
        }
        return dp[n];
    }

    /**
     * 剑指 Offer 14- II. 剪绳子 II
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。
     * 请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
     * <p>
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * <p>
     * 示例 1：
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1
     * <p>
     * 示例 2:
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     */
    public static int cuttingRope2(int n) throws Exception {

        if (n == 1) {
            return n;
        }
        int N = 1000000007;
        BigInteger dp[] = new BigInteger[n + 1];
        Arrays.fill(dp, BigInteger.valueOf(1));
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                BigInteger a = dp[i - j].multiply(BigInteger.valueOf(j));
                int b = j * (i - j);
                BigInteger c = dp[j].multiply(BigInteger.valueOf(i - j));
                BigInteger d = dp[j].multiply(dp[i - j]);
                dp[i] = dp[i].max(a).max(BigInteger.valueOf(b)).max(c).max(d);
            }
        }
        return dp[n].mod(BigInteger.valueOf(N)).intValue();
    }

    /**
     * 剑指 Offer 15. 二进制中1的个数
     * 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
     * <p>
     * 示例 1：
     * <p>
     * 输入：00000000000000000000000000001011
     * 输出：3
     * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
     * 示例 2：
     * <p>
     * 输入：00000000000000000000000010000000
     * 输出：1
     * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
     * 示例 3：
     * <p>
     * 输入：11111111111111111111111111111101
     * 输出：31
     * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
     */
    public int hammingWeight(int n) {
        // Integer 中放法，返回int数中二进制1的个数
        return Integer.bitCount(n);
    }

    public int hammingWeight2(int n) {
        // 位运算符主要针对二进制，它包括了：“与”、“非”、“或”、“异或”。
        // 从表面上看似乎有点像逻辑运算符，但逻辑运算符是针对两个关系运算符来进行逻辑运算，而位运算符主要针对两个二进制数的位进行逻辑运算。
        // &:两个操作数中位都为1，结果才为1，否则结果为0
        // |:两个位只要有一个为1，那么结果就是1，否则就为0
        // ~:如果位为0，结果是1，如果位为1，结果是0
        // ^:两个操作数的位中，相同则结果为0，不同则结果为1

        // 初始化数量统计变量 res = 0 。
        //循环逐位判断： 当 n = 0 时跳出。
        //res += n & 1 ： 若 n & 1 = 1 ，则统计数 resres 加一。
        //n >>= 1 ： 将二进制数字 n 无符号右移一位（ Java 中无符号右移为 ">>>" ） 。
        //返回统计数量 resres 。
        //
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>>= 1;
        }
        return res;
    }

    /**
     * 剑指 Offer 16. 数值的整数次方
     * 实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
     * <p>
     * 示例 1:
     * <p>
     * 输入: 2.00000, 10
     * 输出: 1024.00000
     * 示例 2:
     * <p>
     * 输入: 2.10000, 3
     * 输出: 9.26100
     * 示例 3:
     * <p>
     * 输入: 2.00000, -2
     * 输出: 0.25000
     * 解释: 2-2 = 1/22 = 1/4 = 0.25
     */
    // TODO 笨重的方法，会导致时间超时
    public static double myPow(double x, int n) {

        double res = 1;
        if (n == 0) {
            return 1;
        }
        if (x > 0) {
            if (getN(n)) {
                // x为正数,n为正数
                for (int i = 1; i <= n; i++) {
                    res = res * x;
                }
            } else {
                // x为负数，n为负数
                int k = -n;
                for (int i = 1; i <= k; i++) {
                    res = res * (1 / x);
                }
            }
            return res;
        } else if (x == 0) {
            return 0;
        } else {
            if (getN(n)) {
                // x为负数,n为正数
                for (int i = 1; i <= n; i++) {
                    res = res * x;
                }
            } else {
                // x为负数，n为负数
                int k = -n;
                for (int i = 1; i <= k; i++) {
                    res = res * (1 / x);
                }
            }
            return res;
        }

    }

    public static boolean getN(int n) {
        boolean bool = false;
        if (n > 0) {
            bool = true;
        } else {
            bool = false;
        }
        return bool;
    }

    // 新解法，采用递归，n次方，需要判断n是否为奇数还是偶数
    public static double myPow2(double x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            // 如果不减去1的话会报错
            return 1 / x * myPow2(1 / x, -n - 1);
        }
        return (n % 2 == 0) ? myPow2(x * x, n / 2) : x * myPow2(x * x, n / 2);
    }

    /**
     * 剑指 Offer 17. 打印从1到最大的n位数
     * 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
     * 示例 1:
     * <p>
     * 输入: n = 1
     * 输出: [1,2,3,4,5,6,7,8,9]
     */
    public static int[] printNumbers(int n) {
        int num = 1;
        for (int i = 1; i <= n; i++) {
            num = num * 10;
        }
        int[] res = new int[num - 1];
        for (int i = 1; i < num; i++) {
            res[i - 1] = i;
        }
        return res;
    }

    /**
     * 剑指 Offer 18. 删除链表的节点
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     * <p>
     * 返回删除后的链表的头节点。
     * <p>
     * 注意：此题对比原题有改动
     * <p>
     * 示例 1:
     * <p>
     * 输入: head = [4,5,1,9], val = 5
     * 输出: [4,1,9]
     * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
     * 示例 2:
     * <p>
     * 输入: head = [4,5,1,9], val = 1
     * 输出: [4,5,9]
     * 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
     */
    public ListNode deleteNode(ListNode head, int val) {

        if (head == null) return head;
        // 当链表头等于val 直接返回
        if (head.val == val) return head.next;
        ListNode listNode = head;
        ListNode next = head.next;
        while (next != null && next.val != val) {
            listNode = next;
            next = next.next;
        }
        if (next != null) {
            listNode.next = next.next;
        }
        return head;
    }

    /**
     * 剑指 Offer 19. 正则表达式匹配
     * <p>
     * 请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
     * 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
     * <p>
     * 示例 1:
     * 输入:
     * s = "aa"
     * p = "a"
     * 输出: false
     * 解释: "a" 无法匹配 "aa" 整个字符串。
     * <p>
     * 示例 2:
     * 输入:
     * s = "aa"
     * p = "a*"
     * 输出: true
     * 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
     * <p>
     * 示例 3:
     * 输入:
     * s = "ab"
     * p = ".*"
     * 输出: true
     * 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
     * <p>
     * 示例 4:
     * 输入:
     * s = "aab"
     * p = "c*a*b"
     * 输出: true
     * 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
     * <p>
     * 示例 5:
     * 输入:
     * s = "mississippi"
     * p = "mis*is*p*."
     * 输出: false
     * <p>
     * s 可能为空，且只包含从 a-z 的小写字母。
     * p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。
     * <p>
     * <p>
     * 题解：
     * 使用动态规划。
     * 定义boolean[][] dp = new boolean[s.length() + 1][p.length() + 1]，初始化dp[s.length()][p.length()] = true，表示当两者都为空时匹配。
     * 如何得到dp[i][j]的值？首先判断s.charAt(i)和p.charAt(j)是否匹配，匹配的条件是两个字符相同，或者p.charAt(j)是'.'。然后判断p.charAt(j + 1)是不是'*'，
     * 若是，由于'*'可匹配0个字符，当dp[i][j + 2] == true时dp[i][j] = true，另外当目前的字符匹配且d[i + 1][j] == true时dp[i][j] = true。
     * 如果p.charAt(j + 1)不是'*'，则dp[i][j] = true当且仅当目前的字符匹配且dp[i + 1][j + 1] == true。
     * 最后返回dp[0][0]。
     * <p>
     * Java
     * <p>
     * class Solution {
     * public boolean isMatch(String s, String p) {
     * int sLength = s.length(), pLength = p.length();
     * boolean[][] dp = new boolean[sLength + 1][pLength + 1];
     * dp[sLength][pLength] = true;
     * for (int i = sLength; i >= 0; i--) {
     * for (int j = pLength - 1; j >= 0; j--) {
     * boolean charMatch = i < sLength && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
     * if (j < pLength - 1 && p.charAt(j + 1) == '*')
     * dp[i][j] = dp[i][j + 2] || charMatch && dp[i + 1][j];
     * else
     * dp[i][j] = charMatch && dp[i + 1][j + 1];
     * }
     * }
     * return dp[0][0];
     * }
     * }
     */
    public boolean isMatch(String s, String p) {
        // 将字符串转换成数组
        // matches() 方法用于检测字符串是否匹配给定的正则表达式
        return s.matches(p);
    }

    public boolean isMatch2(String s, String p) {
        // 将字符串转换成数组
        char[] charS = s.toCharArray();
        char[] charP = p.toCharArray();
        for (int i = 0; i < charS.length; i++) {
            // 正则遍历
            for (int j = 0; j < charP.length; j++) {
                // 如果为* 的情况
                if ("*".equals(charP[j])) {
                    // 如果为*，判断前一个是否相等
                    if (charS[i] == charP[j - 1]) {
                        break;
                    }
                } else if (".".equals(charP[j])) {
                    charP[j] = charS[i];
                }
            }
        }
        return false;
    }

    /**
     * 剑指 Offer 20. 表示数值的字符串
     * <p>
     * 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
     * 例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
     * <p>
     * 编码没什么难度，难点在于归纳各种正确的情况
     * （1）‘.’出现正确情况：只出现一次，且在e的前面
     * （2）‘e’出现正确情况：只出现一次，且出现前有数字
     * （3）‘+’‘-’出现正确情况：只能在开头和e后一位
     */
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首位空格
        s = s.trim();
        boolean numBool = false;
        boolean eBool = false;
        boolean operBool = false;
        for (int i = 0; i < s.length(); i++) {
            // 判断是否为数字
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numBool = true;
            }
            // 不能出现两个. ；没有出现过e；
            else if (s.charAt(i) == '.' && !eBool && numBool && !operBool) {
                operBool = true;
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && numBool && !eBool) {
                eBool = true;
                numBool = false;//为了避免123e这种请求，出现e之后就标志为false
            }
            //判定为+-符号，只能出现在第一位或者紧接e后面
            else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {
                //其他情况，都是非法的
            } else {
                return false;
            }
        }
        return numBool;

    }

    /**
     * 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
     * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
     * <p>
     * 示例：
     * 输入：nums = [1,2,3,4]
     * 输出：[1,3,2,4]
     * 注：[3,1,2,4] 也是正确的答案之一。
     */
    public int[] exchange(int[] nums) {
        if (nums.length <= 0) return nums;
        int[] res = new int[nums.length];
        int index = 0;
        // 遍历数组找出奇数和偶数
        for (int i = 0; i < nums.length; i++) {
            // 获取奇数
            if (nums[i] % 2 != 0) {
                res[index] = nums[i];
                index++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            // 获取偶数
            if (nums[i] % 2 == 0) {
                res[index] = nums[i];
                index++;
            }
        }
        return res;
    }

    // 用i当作奇数的索引位置，j为偶数的索引位置。
    public int[] exchange2(int[] nums) {
        int p = 0;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] % 2 == 1) {
                // 停留在偶数位置上
                int temp = nums[i];
                nums[i] = nums[p];
                nums[p] = temp;
                ++p;
            }
            i++;
        }
        return nums;
    }

    /**
     * 剑指 Offer 22. 链表中倒数第k个节点
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * 例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
     * <p>
     * 示例：
     * 给定一个链表: 1->2->3->4->5, 和 k = 2.
     * 返回链表 4->5.
     * 思路：
     * 定义两个链表，第一个链表先走k步，第二个链表从头开始走，当第一个链表走完，第二个链表剩下的就是倒数第k个
     */
    public ListNode getKthFromEnd(ListNode head, int k) {

        ListNode ahead = head;
        ListNode back = head;
        // 头链表先走k步
        while (ahead != null && k > 0) {
            ahead = ahead.next;
            k--;
        }
        while (ahead != null) {
            ahead = ahead.next;
            back = back.next;
        }
        return back;
    }

    /**
     * 剑指 Offer 24. 反转链表
     * <p>
     * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
     * 示例:
     * 输入: 1->2->3->4->5->NULL
     * 输出: 5->4->3->2->1->NULL
     */
    public ListNode reverseList(ListNode head) {

        if (head == null) {
            return head;
        }
        Stack<ListNode> stack = new Stack();
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        ListNode listNode = stack.pop();
        ListNode lastNode = listNode;
        while (!stack.empty()) {
            ListNode cur = stack.pop(); // 弹出当前节点
            lastNode.next = cur; // 将返回节点下一个存放当前节点
            lastNode = cur; // 临时存储前一个节点
        }
        // 这里要注意：最后一个节点赋为null（不然会造成死循环）
        lastNode.next = null;
        return listNode;
    }

    /**
     * 剑指 Offer 25. 合并两个排序的链表
     * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * 示例1：
     * 输入：1->2->4, 1->3->4
     * 输出：1->1->2->3->4->4
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // 有空链表，返回不空者即可
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        ListNode listNode = new ListNode(0);
        ListNode node = listNode;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            } else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        // 合并剩余节点
        node.next = l1 != null ? l1 : l2;
        return listNode.next;
    }

    /**
     * 剑指 Offer 26. 树的子结构
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
     * <p>
     * B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     * <p>
     * 例如:
     * 给定的树 A:
     * <p>
     *      3
     *     / \
     *    4   5
     *   / \
     *  1   2
     * 给定的树 B：
     * <p>
     *    4 
     *   /
     *  1
     * 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
     * <p>
     * 示例 1：
     * <p>
     * 输入：A = [1,2,3], B = [3,1]
     * 输出：false
     * 示例 2：
     * <p>
     * 输入：A = [3,4,5,1,2], B = [4,1]
     * 输出：true
     */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) return false;
        // 我们规定树的子结构必须是 B 树的结构和结点值完全与 A 相同
        // 如果B树和A树相同, 那么也是一种子结构
        // 我们可以分为三种情况判断
        // 1. A树与B树完全相等
        // 2. A的左子树与B树完全相等
        // 3. A的右子树与B树完全相等
        return dfs(A, B) || isSubStructure(A.right, B) || isSubStructure(A.left, B);
    }

    public boolean dfs(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
    }

    /**
     * 剑指 Offer 27. 二叉树的镜像
     * <p>
     * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
     * <p>
     * 例如输入：
     * <p>
     *      4
     *    /   \
     *   2     7
     *  / \   / \
     * 1   3 6   9
     * 镜像输出：
     * <p>
     *      4
     *    /   \
     *   7     2
     *  / \   / \
     * 9   6 3   1
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：root = [4,2,7,1,3,6,9]
     * 输出：[4,7,2,9,6,3,1]
     */
    public TreeNode mirrorTree(TreeNode root) {

        if (root == null) return null;
        TreeNode tempNode = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(tempNode);
        return root;
    }

    /**
     * 剑指 Offer 28. 对称的二叉树
     * <p>
     * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
     * <p>
     * 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
     * <p>
     *     1
     *    / \
     *   2   2
     *  / \ / \
     * 3  4 4  3
     * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
     * <p>
     *     1
     *    / \
     *   2   2
     *    \   \
     *    3    3
     * <p>
     * 示例 1：
     * <p>
     * 输入：root = [1,2,2,3,4,4,3]
     * 输出：true
     * 示例 2：
     * <p>
     * 输入：root = [1,2,2,null,3,null,3]
     * 输出：false
     * <p>
     * 思路：
     * 做递归思考三步：
     * <p>
     * 递归的函数要干什么？
     * 函数的作用是判断传入的两个树是否镜像。
     * 输入：TreeNode left, TreeNode right
     * 输出：是：true，不是：false
     * 递归停止的条件是什么？
     * 左节点和右节点都为空 -> 倒底了都长得一样 ->true
     * 左节点为空的时候右节点不为空，或反之 -> 长得不一样-> false
     * 左右节点值不相等 -> 长得不一样 -> false
     * 从某层到下一层的关系是什么？
     * 要想两棵树镜像，那么一棵树左边的左边要和二棵树右边的右边镜像，一棵树左边的右边要和二棵树右边的左边镜像
     * 调用递归函数传入左左和右右
     * 调用递归函数传入左右和右左
     * 只有左左和右右镜像且左右和右左镜像的时候，我们才能说这两棵树是镜像的
     * 调用递归函数，我们想知道它的左右孩子是否镜像，传入的值是root的左孩子和右孩子。这之前记得判个root==null。
     */
    public boolean isSymmetric(TreeNode root) {

        if (root == null) return true;
        return dfs2(root.left, root.right);
    }

    public boolean dfs2(TreeNode rootA, TreeNode rootB) {
        if (rootA == null && rootB == null) return true;
        if (rootA == null || rootB == null) return false;
        return rootA.val == rootB.val && dfs2(rootA.left, rootB.right) && dfs2(rootA.right, rootB.left);
    }

    /**
     * 剑指 Offer 29. 顺时针打印矩阵
     * <p>
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
     * 示例 1：
     * <p>
     * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,2,3,6,9,8,7,4,5]
     * 示例 2：
     * <p>
     * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
     * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     */
    public static int[] spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new int[0];
        }
        // 行
        int row = matrix.length;
        // 列
        int clo = matrix[0].length;
        // 定义总长度的数组
        int[] res = new int[row * clo];
        // 定义结果数组的指针
        int pIndex = 0;
        // 行坐标
        int rIndex = 0;
        // 列坐标
        int cIndex = 0;
        while (rIndex <= row && cIndex <= clo) {
            // 从左往右
            for (int j = cIndex; j < clo; j++) {
                res[pIndex++] = matrix[rIndex][j];
                if (pIndex == res.length) {
                    return res;
                }
            }
            // 从上往下
            for (int i = rIndex + 1; i < row - 1; i++) {
                res[pIndex++] = matrix[i][clo - 1];
                if (pIndex == res.length) {
                    return res;
                }
            }
            // 从右往左
            for (int j = clo - 1; j >= cIndex; j--) {
                res[pIndex++] = matrix[row - 1][j];
                if (pIndex == res.length) {
                    return res;
                }
            }
            // 从下往上
            for (int i = row - 2; i > rIndex; i--) {
                res[pIndex++] = matrix[i][cIndex];
                if (pIndex == res.length) {
                    return res;
                }
            }
            rIndex++;
            cIndex++;
            row--;
            clo--;
        }
        return res;
    }

    /**
     * 剑指 Offer 30. 包含min函数的栈
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
     * 示例:
     * <p>
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.min();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.min();   --> 返回 -2.
     * <p>
     * 将 min() 函数复杂度降为 O(1)O(1) ，可通过建立辅助栈实现；
     * 数据栈 A ： 栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
     * 辅助栈 B ： 栈 B 中存储栈 A 中所有 非严格降序 的元素，则栈 A 中的最小元素始终对应栈 B 的栈顶元素，即 min() 函数只需返回栈 B 的栈顶元素即可。
     * <p>
     * push(x) 函数： 重点为保持栈 BB 的元素是 非严格降序 的。
     * <p>
     * 将 xx 压入栈 A （即 A.add(x) ）；
     * 若 ① 栈 B 为空 或 ② xx 小于等于 栈 B 的栈顶元素，则将 x 压入栈 B （即 B.add(x) ）。
     * pop() 函数： 重点为保持栈 A,B 的 元素一致性 。
     * <p>
     * 执行栈 A 出栈（即 A.pop() ），将出栈元素记为 yy ；
     * 若 y 等于栈 B 的栈顶元素，则执行栈 B 出栈（即 B.pop() ）。
     * top() 函数： 直接返回栈 A 的栈顶元素即可，即返回 A.peek() 。
     * <p>
     * min() 函数： 直接返回栈 B 的栈顶元素即可，即返回 B.peek() 。
     */
    static class MinStack {

        Stack<Integer> A, B;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            A = new Stack<>();
            B = new Stack<>();
        }

        // 入栈
        public void push(int x) {
            A.add(x);
            // 如果入栈元素等于或者小于B的栈顶元素，B栈入栈，保证B栈中跟A栈中对应元素，B中栈顶元素最小
            if (B.empty() || x <= B.peek()) {
                B.add(x);
            }
        }

        // 出栈
        public void pop() {
            // 如果A中出栈元素 等于 B中栈顶元素，B也要出栈
            if (A.pop().equals(B.peek())) {
                B.pop();
            }
        }

        // 返回栈顶元素
        public int top() {
            return A.peek();
        }

        // 返回栈中最小元素
        public int min() {
            return B.peek();
        }
    }

    /**
     * 剑指 Offer 31. 栈的压入、弹出序列
     * <p>
     * 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
     * 例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
     * <p>
     * 示例 1：
     * 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
     * 输出：true
     * 解释：我们可以按以下顺序执行：
     * push(1), push(2), push(3), push(4), pop() -> 4,
     * push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
     * <p>
     * 示例 2：
     * 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
     * 输出：false
     * 解释：1 不能在 2 之前弹出。
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> auxiliaryStack = new Stack<>();
        int index = 0;
        for (int num : pushed) {
            auxiliaryStack.push(num);
            while (!auxiliaryStack.empty() && auxiliaryStack.peek() == popped[index]) {
                auxiliaryStack.pop();
                index++;
            }
        }
        return auxiliaryStack.empty();
    }

    /**
     * 剑指 Offer 32 - I. 从上到下打印二叉树
     * 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
     * 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。
     * BFS 通常借助 队列 的先入先出特性来实现。
     * <p>
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回：
     * <p>
     * [3,9,20,15,7]
     */
    public int[] levelOrder(final TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {
            {
                add(root);
            }
        };
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            arrayList.add(treeNode.val);
            if (treeNode.left != null) queue.add(treeNode.left);
            if (treeNode.right != null) queue.add(treeNode.right);
        }
        int[] res = new int[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            res[i] = arrayList.get(i);
        }
        return res;
    }

    /**
     * 剑指 Offer 32 - II. 从上到下打印二叉树 II
     * 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
     * <p>
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回其层次遍历结果：
     * <p>
     * [
     * [3],
     * [9,20],
     * [15,7]
     * ]
     */
    public List<List<Integer>> levelOrder2(final TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{
            add(root);
        }};
        while (!queue.isEmpty()) {
            List<Integer> integerList = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode treeNode = queue.poll();
                integerList.add(treeNode.val);
                if (treeNode.left != null) queue.add(treeNode.left);
                if (treeNode.right != null) queue.add(treeNode.right);
            }
            lists.add(integerList);
        }
        return lists;
    }

    /**
     * 剑指 Offer 32 - III. 从上到下打印二叉树 III
     * 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印(奇数)，第二层按照从右到左的顺序打印（偶数），第三行再按照从左到右的顺序打印，其他行以此类推。
     * <p>
     * 例如:
     * 给定二叉树: [3,9,20,null,null,15,7],
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回其层次遍历结果：
     * <p>
     * [
     * [3],
     * [20,9],
     * [15,7]
     * ]
     */
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            // LinkedList 可以选择添加方式
            LinkedList<Integer> integerList = new LinkedList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode treeNode = queue.poll();
                if (res.size() % 2 == 0) {
                    // 偶数（奇数层）：从右到左
                    integerList.addLast(treeNode.val);
                } else {
                    // 奇数（偶数层）：从左到右
                    integerList.addFirst(treeNode.val);
                }
                if (treeNode.left != null) queue.add(treeNode.left);
                if (treeNode.right != null) queue.add(treeNode.right);
            }
            res.add(integerList);
        }
        return res;
    }

    /**
     * 剑指 Offer 33. 二叉搜索树的后序遍历序列
     * <p>
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     * <p>
     * 参考以下这颗二叉搜索树：
     * <p>
     * 5
     * / \
     * 2   6
     * / \
     * 1   3
     * 示例 1：
     * <p>
     * 输入: [1,6,3,2,5]
     * 输出: false
     * 示例 2：
     * <p>
     * 输入: [1,3,2,6,5]
     * 输出: true
     * <p>
     * 后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
     * 二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。
     */
    public boolean verifyPostorder(int[] postorder) {

        return recur(postorder, 0, postorder.length - 1);
    }

    boolean recur(int[] postorder, int i, int j) {
        if (i >= j) return true;
        // i 为二叉树开始的头节点索引，j 为二叉树根节点索引
        // m为后序遍历过程中左右子树的分界
        int index = i;
        // 左子树
        while (postorder[index] < postorder[j]) index++;
        // 此时已经得到左子树的节点范围，rightIndex用于根右子树节点进行比较
        int rightIndex = index;
        // 右子树
        while (postorder[index] > postorder[j]) index++;
        // index == j 判断索引是否到达最后一个位置
        return index == j && recur(postorder, i, rightIndex - 1) && recur(postorder, rightIndex, j - 1);
    }

    /**
     * 剑指 Offer 34. 二叉树中和为某一值的路径
     * <p>
     * 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
     * 示例:
     * 给定如下二叉树，以及目标和 sum = 22，
     * <p>
     * 5
     * / \
     * 4   8
     * /   / \
     * 11  13  4
     * /  \    / \
     * 7    2  5   1
     * 返回:
     * [
     * [5,4,11,2],
     * [5,8,4,5]
     * ]
     */
    // 定义结果的返回路径
    List<List<Integer>> resPathSumList = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 定义路径
        LinkedList<Integer> path = new LinkedList<>();
        pathRout(root, sum, path);
        return resPathSumList;
    }

    public void pathRout(TreeNode root, int sum, LinkedList<Integer> path) {
        if (root == null) return;
        path.add(root.val);
        sum -= root.val;
        if (sum == 0 && root.left == null && root.right == null) {
            resPathSumList.add(new LinkedList(path));
        }
        pathRout(root.left, sum, path);
        pathRout(root.right, sum, path);
        path.removeLast();
    }

    /**
     * 剑指 Offer 35. 复杂链表的复制
     * <p>
     * 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
     * <p>
     * 示例 1：
     * 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
     * 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
     * <p>
     * 示例 2：
     * 输入：head = [[1,1],[2,1]]
     * 输出：[[1,1],[2,1]]
     * <p>
     * 示例 3：
     * 输入：head = [[3,null],[3,0],[3,null]]
     * 输出：[[3,null],[3,0],[3,null]]
     * <p>
     * 示例 4：
     * 输入：head = []
     * 输出：[]
     * 解释：给定的链表为空（空指针），因此返回 null。
     */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        if (head == null) {
            return head;
        }
        // 完成链表节点的复,尽量避免在原数据上进行数据修改
        Node node = head;
        HashMap<Node, Node> hashMap = new HashMap<>();
        while (node != null) {
            // hashMap存放node节点，new Node 为新创建节点，节点的val确定，next 和 random 为null
            hashMap.put(node, new Node(node.val));
            node = node.next;
        }

        node = head;
        while (node != null) {
            // 在hashmap中找到对应的next节点
            hashMap.get(node).next = hashMap.get(node.next);
            // 在hashmap中找到对应的random节点
            hashMap.get(node).random = hashMap.get(node.random);
            node = node.next;
        }
        return hashMap.get(head);
    }

    /**
     * 剑指 Offer 36. 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
     * 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
     * <p>
     * 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
     * <p>
     * 本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。
     * 将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
     * <p>
     * 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点；
     * 双向链表： 在构建相邻节点（设前驱节点 pre ，当前节点 cur ）关系时，不仅应 pre.right = cur ，也应 cur.left = pre 。
     * 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。
     */

    // TODO 如果是双向链表、排序链表的解决方案
    class NodeTreeToDoublyList {
        public int val;
        public NodeTreeToDoublyList left;
        public NodeTreeToDoublyList right;

        public NodeTreeToDoublyList() {
        }

        public NodeTreeToDoublyList(int _val) {
            val = _val;
        }

        public NodeTreeToDoublyList(int _val, NodeTreeToDoublyList _left, NodeTreeToDoublyList _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    // 定义全局头尾节点
    NodeTreeToDoublyList head, tail;

    public NodeTreeToDoublyList treeToDoublyList(NodeTreeToDoublyList root) {
        if (root == null) return null;
        dfsTreeNodeDoublyList(root);
        // 进行头尾节点互相指向
        head.left = tail; // 左侧指向
        tail.right = head; // 右侧指向
        return head;
    }

    public void dfsTreeNodeDoublyList(NodeTreeToDoublyList root) {

        if (root == null) return;
        dfsTreeNodeDoublyList(root.left);
        //  head >> tail >> root
        if (tail == null) head = root;
        else tail.right = root;
        // 指定root的左侧节点
        root.left = tail;

        // 将尾节点 tail 替换为root
        tail = root;

        dfsTreeNodeDoublyList(root.right);
    }

    /**
     * 剑指 Offer 37. 序列化二叉树
     * 请实现两个函数，分别用来序列化和反序列化二叉树。
     *
     * 示例: 
     *
     * 你可以将以下二叉树：
     *
     *          1
     *        /  \
     *      2     3
     *     / \    / \
     *  null null 4   5
     *
     * 序列化为 "[1,2,3,null,null,4,5]"
     *
     */

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    // Encodes a tree to a single string.
    // 序列化
    public String serialize(final TreeNode root) {
        if (root == null) return "null";
        StringBuilder res = new StringBuilder();
        // 将树添加到队列中
        Queue<TreeNode> queue = new LinkedList<TreeNode>() {{
            add(root);
        }};
        while (!queue.isEmpty()) {
            // 将队列中的 treeNode 弹出
            TreeNode treeNode = queue.poll();
            // 判断节点是否为空
            if (treeNode == null) {
                // 节点为空，字符串追加null
                res.append("null,");
                continue;
            }
            // 字符串追加节点值
            res.append(treeNode.val + ",");
            // 向队列中添加左右节点
            queue.add(treeNode.left);
            queue.add(treeNode.right);
        }
        return res.toString();
    }

    // Decodes your encoded data to tree.
    // 反序列化
    public TreeNode deserialize(String data) {

        // 如果字符串不为空
        if (data == "null") return null;
        Queue<TreeNode> queue = new LinkedList<>();
        String[] strings = data.split(",");
        // 找到根节点
        if ("null".equals(strings[0])) return null;
        TreeNode root = new TreeNode(Integer.parseInt(strings[0]));
        queue.add(root);
        for (int i = 1; i < strings.length; i++) {
            // 弹出根节点
            TreeNode rootTreeNode = queue.poll();
            if (!"null".equals(strings[i])) {
                TreeNode left = new TreeNode(Integer.parseInt(strings[i]));
                rootTreeNode.left = left;
                queue.add(left);
            }
            // TODO 上面如果不为空就是左子节点的值，这里是右子节点的值，注意这里有个i++，右节点会越界
            if (!"null".equals(strings[++i])) {
                TreeNode right = new TreeNode(Integer.parseInt(strings[i]));
                rootTreeNode.right = right;
                queue.add(right);
            }
        }
        return root;
    }

    /**
     * 剑指 Offer 38. 字符串的排列
     * <p>
     * 输入一个字符串，打印出该字符串中字符的所有排列。
     * <p>
     * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
     * <p>
     * 示例:d
     * 输入：s = "abc"
     * 输出：["abc","acb","bac","bca","cab","cba"]
     */

    // List<String> list = new LinkedList<>();
    List<String> list = new ArrayList<>();
    char[] chars;

    public String[] permutation(String s) {

        // 将字符串转换成char数组
        chars = s.toCharArray();
        dfsChars(0);
        return list.toArray(new String[list.size()]);
    }

    public void dfsChars(int index) {

        if (index == chars.length - 1) {
            list.add(String.valueOf(chars));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < chars.length; i++) {
            // 当 hashSet 中存在该元素，跳出当前循环，执行下一次循环
            if (set.contains(chars[i])) continue;
            set.add(chars[i]);
            // 将 i 位置的 dfsChar[i] 固定在第 index 位置
            // 进行数据交换
            exchange(i, index);
            // TODO 递归调用
            dfsChars(index + 1);
            // 将数据还原回去
            exchange(i, index); // 恢复交换
        }
    }

    void exchange(int i, int index) {
        char temp = chars[i];
        chars[i] = chars[index];
        chars[index] = temp;
    }

    /**
     * 剑指 Offer 39. 数组中出现次数超过一半的数字
     * <p>
     * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * 示例 1:
     * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
     * 输出: 2
     * <p>
     * 思路：
     * 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N) 。
     * 数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。
     * 摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ，为本题的最佳解法。
     */
    public int majorityElement(int[] nums) {

        if (nums == null) return 0;
        int res = 0;
        int max = 0;
        for (int num : nums) {
            int count = 0;
            for (int i : nums) {
                if (num == i) {
                    count = count + 1;
                }
            }
            if (max < count) {
                max = count;
                res = num;
            }
        }
        return res;
    }

    public int majorityElement2(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) x = num;
            if (num == x) votes = votes + 1;
            else votes = votes - 1;
        }
        return x;
    }

    /**
     * 剑指 Offer 40. 最小的k个数
     * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
     * 示例 1：
     * <p>
     * 输入：arr = [3,2,1], k = 2
     * 输出：[1,2] 或者 [2,1]
     * 示例 2：
     * <p>
     * 输入：arr = [0,1,2,1], k = 1
     * 输出：[0]
     */
    public int[] getLeastNumbers(int[] arr, int k) {

        int[] res = arr;
        int[] result = new int[k];
        if (arr == null || k <= 0) return result;
        Arrays.sort(res);
        for (int i = 0; i < k; i++) {
            result[i] = res[i];
        }
        return result;
    }

    /**
     * 思路：
     * 用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，
     * 就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可
     * <p>
     * PriorityQueue类在Java1.5中引入并作为 Java Collections Framework 的一部分。PriorityQueue是基于优先堆的一个无界队列，
     * 这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化时排序。
     * 优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用Java Comparable和Comparator接口给对象排序，
     * 并且在排序时会按照优先级处理其中的元素。
     * 优先队列的头是基于自然排序或者Comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。
     * <p>
     * TODO add()\offer():两者都是往队列尾部插入元素，不同的时候，当超出队列界限的时候，add（）方法是抛出异常让你处理，而offer（）方法是直接返回false
     */

    public int[] getLeastNumbers2(int[] arr, int k) {
        int[] result = new int[k];
        if (k <= 0) return result;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        for (int i = 0; i < k; i++) {
            queue.offer(arr[i]);
        }
        for (int i = k; i < arr.length; ++i) {
            if (queue.peek() > arr[i]) {
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            result[i] = queue.poll();
        }
        return result;
    }

    /**
     * 剑指 Offer 41. 数据流中的中位数
     * <p>
     * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
     * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
     * <p>
     * 例如，
     * <p>
     * [2,3,4] 的中位数是 3
     * <p>
     * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
     * <p>
     * 设计一个支持以下两种操作的数据结构：
     * <p>
     * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
     * double findMedian() - 返回目前所有元素的中位数。
     * 示例 1：
     * <p>
     * 输入：
     * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
     * [[],[1],[2],[],[3],[]]
     * 输出：[null,null,null,1.50000,null,2.00000]
     * 示例 2：
     * <p>
     * 输入：
     * ["MedianFinder","addNum","findMedian","addNum","findMedian"]
     * [[],[2],[],[3],[]]
     * 输出：[null,null,2.00000,null,2.50000]
     * <p>
     * TODO 思路：
     * 使用最大堆和最小堆实现在O(1)时间返回中位数. 插入数据的时间复杂度是O(n)
     * TODO 首先要保证数据平均分配到两个堆中, 因此两个堆中的元素的个数相差最多为1
     * 为实现平均分配, 可以在数据的总数目是偶数时,把新数据插入最小堆; 在数据的总数目是奇数时,把新数据插入最大堆
     * 约束条件:要始终保证最小堆的堆顶元素比最大堆的堆顶元素大
     * TODO 如果数据的总数目是偶数时, 新数据应该插入最小堆, 但是如果新数据比最大堆的堆顶元素小, 也就是新数据插入最小堆会破坏约束条件, 此时可以将新数据插入最大堆,
     * 然后再将最大堆的堆顶元素插入最小堆
     * TODO 如果数据的总数目是奇数时, 新数据应该插入最大堆, 但是如果该元素比最小堆的堆顶元素大, 也就是新数据插入最大堆会破坏约束条件, 此时可以将新数据插入最小堆,
     * 然后再把最小堆的堆顶元素插入最大堆
     */
    class MedianFinder {
        // 最小堆
        PriorityQueue<Integer> queueSmall;
        // 大堆
        PriorityQueue<Integer> queueBig;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            // 初始化的时候先定义大小堆
            queueSmall = new PriorityQueue<>();
            queueBig = new PriorityQueue<Integer>(new Comparator<Integer>() {
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
        }

        // 从数据流中添加一个整数到数据结构中。
        // TODO offer，add区别：
        //一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
        //这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
        //
        // TODO poll，remove区别：
        //remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似，
        //但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
        //
        // TODO peek，element区别：
        //element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null
        public void addNum(int num) {
            // 当为偶数时:
            // 新数据应该插入最小堆, 但是如果新数据比最大堆的堆顶元素小, 也就是新数据插入最小堆会破坏约束条件, 此时可以将新数据插入最大堆, 然后再将最大堆的堆顶元素插入最小堆
            if (queueBig.size() == queueSmall.size() || queueSmall.isEmpty()) {
                if (!queueBig.isEmpty() && num < queueBig.peek()) {
                    queueBig.add(num);
                    num = queueBig.poll();
                }
                queueSmall.add(num);
            }
            // 新数据应该插入最大堆, 但是如果该元素比最小堆的堆顶元素大, 也就是新数据插入最大堆会破坏约束条件, 此时可以将新数据插入最小堆, 然后再把最小堆的堆顶元素插入最大堆
            else {
                if (num > queueSmall.peek() && !queueSmall.isEmpty()) {
                    queueSmall.add(num);
                    num = queueSmall.poll();
                }
                queueBig.add(num);
            }
        }

        // 返回目前所有元素的中位数
        public double findMedian() {
            return queueSmall.size() > queueBig.size() ? queueSmall.peek() : (queueBig.peek() + queueSmall.peek()) / 2.0;
        }
    }

    /**
     * 剑指 Offer 42. 连续子数组的最大和
     * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
     * <p>
     * 要求时间复杂度为O(n)。
     * 示例1:
     * <p>
     * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     */
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }

    /**
     * 剑指 Offer 43. 1～n 整数中 1 出现的次数
     * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
     * <p>
     * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
     * <p>
     * 示例 1：
     * <p>
     * 输入：n = 12
     * 输出：5
     * 示例 2：
     * <p>
     * 输入：n = 13
     * 输出：6
     */
    public static int countDigitOne(int n) {
        int count = 0;
        for (int i = 1; i <= n; i++) {
            // 数字转换成字符串
            String str = String.valueOf(i);
            String[] strings = str.split("");
            for (String s : strings) {
                if ("1".equals(s)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static int countDigitOne1(int n) {
        int high = n / 10;
        int low = 0;
        int cur = n % 10;
        int digit = 1;
        int count = 0;
        while (high != 0 || cur != 0) {
            if (cur == 0) count += high * digit;
            else if (cur == 1) count += high * digit + low + 1;
            else count += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return count;
    }

    /**
     * 剑指 Offer 44. 数字序列中某一位的数字
     * 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
     * <p>
     * 请写一个函数，求任意第n位对应的数字。
     * <p>
     * 示例 1：
     * 输入：n = 3
     * 输出：3
     * <p>
     * 示例 2：
     * 输入：n = 11
     * 输出：0
     */
    public static int findNthDigit(int n) {
        long start = 1; // 开始数字
        long count = 9; // 开始时的区间个数
        int digit = 1; // 位数
        while (n > count) {
            n -= count;
            start = start * 10;
            digit = digit + 1;
            count = start * digit * 9;
        }
        // 遍历完成后就找到了一个区间，从区间中找到第n位数，并返回
        // 找到所在数,n-1 表示剩余区间长度，（n-1）/digit 表示：需要的n个位数除以位数，表示start需要加上几个
        long num = start + (n - 1) / digit;
        // 转换成字符串
        String str = String.valueOf(num);
        String[] strings = str.split("");
        // 取余
        int index = (n - 1) % digit;
        System.out.println(Integer.valueOf(strings[index]));
        return Integer.valueOf(strings[index]);
    }

    /**
     * 剑指 Offer 45. 把数组排成最小的数
     * 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
     * <p>
     * 示例 1:
     * 输入: [10,2]
     * 输出: "102"
     * <p>
     * 示例 2:
     * 输入: [3,30,34,5,9]
     * 输出: "3033459"
     * <p>
     * TODO Java8的新特性 lambda表达式（闭包）  Collections.sort(listStr,(s1,s2)->(s1+s2).compareTo(s2+s1));
     * TODO 且List接口也直接提供了sort方法      listStr.sort((s1,s2)->(s1+s2).compareTo(s2+s1));
     * <p>
     * 思路：
     * 初始化： 字符串列表 strsstrs ，保存各数字的字符串格式；
     * 列表排序： 应用以上 “排序判断规则” ，对 strsstrs 执行排序；
     * 返回值： 拼接 strsstrs 中的所有字符串，并返回。
     */
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder stringBuilder = new StringBuilder();
        for (String s : strs) {
            stringBuilder.append(s);
        }
        return stringBuilder.toString();
    }

    /**
     * 剑指 Offer 46. 把数字翻译成字符串
     * 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。
     * 请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
     * <p>
     * 示例 1:
     * 输入: 12258
     * 输出: 5
     * 解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
     */
    public int translateNum(int num) {
        String str = String.valueOf(num);
        return dfsTrans(0, str);
    }

    public int dfsTrans(int index, String string) {
        if (index >= string.length() - 1) return 1;
        // 单独翻译
        int sum = dfsTrans(index + 1, string);
        // 判断两个一起是否能翻译
        String troubleStr = string.substring(index, index + 2);
        if (troubleStr.compareTo("10") >= 0 && troubleStr.compareTo("25") <= 0) {
            sum += dfsTrans(index + 2, string);
        }
        return sum;
    }

    public static int translateNum2(int num) {
        //如果num小于10了，也就没有得拆分了，只有一种情况，例如数字 5 ，只有 f 这个字母表示
        if (num < 10) return 1;
        int res = num % 100;
        // 12805
        if (res < 10) {
            return translateNum2(num / 10);
        } else if (res < 26) {
            return translateNum2(num / 10) + translateNum2(num / 100);
        } else {
            return translateNum2(num / 10);
        }
    }

    /**
     * 剑指 Offer 47. 礼物的最大价值
     * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、
     * 直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
     * <p>
     * 示例 1:
     * 输入:
     * [
     *   [1,3,1],
     *   [1,5,1],
     *   [4,2,1]
     * ]
     * 输出: 12
     * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
     */
    public int maxValue(int[][] grid) {
        int row = grid.length;
        int clo = grid[0].length;
        int[] dp = new int[row + 1];
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < clo; j++) {
                dp[i] = Math.max(grid[i][j + 1], grid[i + 1][j]) + grid[i - 1][j - 1];
            }
        }

        return dp[row];
    }

    public int maxValue2(int[][] grid) {
        int row = grid.length;
        int clo = grid[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < clo; j++) {
                if (i == 0 && j == 0) continue;
                if (i == 0 && j > 0) grid[i][j] += grid[i][j - 1];
                if (i > 0 && j == 0) grid[i][j] += grid[i - 1][j];
                if (i > 0 && j > 0) grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]);
            }
        }
        return grid[row - 1][clo - 1];
    }

    /**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     * <p>
     * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
     * <p>
     * 示例 1:
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * <p>
     * 示例 2:
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * <p>
     * 示例 3:
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0 || s.length() == 1) return s.length();
        int start = 0;
        int max = 0;
        String[] strings = s.split("");
        for (int i = 1; i < strings.length; i++) {
            for (int j = start; j < i; j++) {
                if (strings[i].equals(strings[j])) {
                    start = j + 1;
                    break;
                }
            }
            max = Math.max(max, i - start + 1);
        }
        return max;
    }

    /**
     * 剑指 Offer 49. 丑数
     * 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
     * <p>
     * 示例:
     * 输入: n = 10
     * 输出: 12
     * 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
     */
    public int nthUglyNumber(int n) {
        if (n <= 0) return 0;
        int[] arr = new int[n];
        arr[0] = 1;
        int index2 = 0;
        int index3 = 0;
        int index5 = 0;
        for (int index = 1; index < n; index++) {
            arr[index] = Math.min(arr[index2] * 2, Math.min(arr[index3] * 3, arr[index5] * 5));
            if (arr[index2] * 2 == arr[index]) index2 += 1;
            if (arr[index3] * 3 == arr[index]) index3 += 1;
            if (arr[index5] * 5 == arr[index]) index5 += 1;
        }
        return arr[n - 1];
    }

    /**
     * 剑指 Offer 50. 第一个只出现一次的字符
     * <p>
     * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
     * 示例:
     * s = "abaccdeff"
     * 返回 "b"
     * <p>
     * s = ""
     * 返回 " "
     */
    public char firstUniqChar(String s) {
        char[] chars = s.toCharArray();
        HashMap<Character, Boolean> hashMap = new HashMap<>();
        for (char c : chars) {
            // 判断hashMap.containsKey(c)，hashmap是否已经包含有key，如果包含为true，不包含为false
            hashMap.put(c, hashMap.containsKey(c));
        }
        for (char c : chars) {
            if (!hashMap.get(c)) return c;
        }
        return ' ';
    }

    /**
     * 剑指 Offer 51. 数组中的逆序对
     * <p>
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     * <p>
     * 示例 1:
     * 输入: [7,5,6,4]
     * 输出: 5
     * <p>
     * TODO 归并排序
     */
    public static int reversePairs(int[] nums) {
        // 复制数组
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        int[] temp = new int[len];
        int count = reversePairsSort(nums, 0, len - 1, temp);
        return count;
    }

    public static int reversePairsSort(int[] nums, int start, int end, int[] temp) {
        if (start == end) {
            return 0;
        }

        int mid = start + (end - start) / 2;
        // 对数组进行拆分
        int leftCount = reversePairsSort(nums, start, mid, temp);
        int rightCount = reversePairsSort(nums, mid + 1, end, temp);

        if (nums[mid] <= nums[mid + 1]) {
            return leftCount + rightCount;
        }

        // 对左右子数组进行合并，计算count
        int mergeCount = reversePairsMerge(nums, start, end, mid, temp);
        return leftCount + rightCount + mergeCount;
    }

    public static int reversePairsMerge(int[] nums, int left, int right, int mid, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        // 左子数组索引
        int indexLeft = left;
        int indexRight = mid + 1;
        int count = 0;

        for (int k = left; k <= right; k++) {
            // 当左侧指针等于mid
            if (indexLeft == mid + 1) {
                nums[k] = temp[indexRight];
                indexRight++;
            } else if (indexRight == right + 1) {
                nums[k] = temp[indexLeft];
                indexLeft++;
            } else if (temp[indexLeft] <= temp[indexRight]) {
                nums[k] = temp[indexLeft];
                indexLeft++;
            } else {
                nums[k] = temp[indexRight];
                indexRight++;
                count += (mid - indexLeft + 1);
            }
        }
        return count;
    }

    // TODO 第二种解法（自己所能理解的）
    public static int reversePairs2(int[] nums) {
        int len = nums.length;
        if (len < 2) return 0;
        int count = sort(nums, 0, len - 1);
        return count;
    }

    public static int sort(int[] nums, int start, int end) {
        if (start == end) return 0;
        int mid = start + (end - start) / 2;
        int leftCount = sort(nums, start, mid);
        int rightCount = sort(nums, mid + 1, end);

        if (nums[mid] <= nums[mid + 1]) {
            return leftCount + rightCount;
        }

        int crossCount = mergeSort(nums, start, end, mid);
        return leftCount + rightCount + crossCount;
    }

    public static int mergeSort(int[] nums, int left, int right, int mid) {

        int[] temp = new int[nums.length];

        int indexLeft = left;
        int indexRight = mid + 1;
        int k = left;

        int count = 0;
        while (indexLeft <= mid && indexRight <= right) {
            if (nums[indexLeft] <= nums[indexRight]) {
                // 左侧数组小于右侧数组
                temp[k] = nums[indexLeft];
                k++;
                indexLeft++;
            } else {
                // 左侧数组大于右侧数组
                temp[k] = nums[indexRight];
                k++;
                indexRight++;
                count += (mid - indexLeft + 1);
            }
        }
        // 当右侧数组走完
        while (indexLeft <= mid) {
            temp[k++] = nums[indexLeft++];
        }
        // 当左侧数组走完
        while (indexRight <= right) {
            temp[k++] = nums[indexRight++];
        }
        // 还原赋值给原始数组
        for (int i = left; i <= right; i++) {
            nums[i] = temp[i];
        }
        return count;
    }

    /**
     * 剑指 Offer 52. 两个链表的第一个公共节点
     * 输入两个链表，找出它们的第一个公共节点。
     * <p>
     * 例1：
     * 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
     * 输出：Reference of the node with value = 8
     * 输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
     * <p>
     * 例2：
     * 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
     * 输出：Reference of the node with value = 2
     * 输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
     * <p>
     * 例3：
     * 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
     * 输出：null
     * 输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
     * 解释：这两个链表不相交，因此返回 null。
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) return null;
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

    /**
     * 剑指 Offer 53 - I. 在排序数组中查找数字 I
     * 统计一个数字在排序数组中出现的次数。
     * <p>
     * 示例 1:
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     * <p>
     * 示例 2:
     * 输入: nums = [5,7,7,8,8,10], target = 6
     * 输出: 0
     */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int num : nums) {
            if (num == target) count += 1;
        }
        return count;
    }

    /**
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * <p>
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     * <p>
     * 示例 1:
     * 输入: [0,1,3]
     * 输出: 2
     * <p>
     * 示例 2:
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     * <p>
     * 思路:
     * TODO 二分查找
     */
    public int missingNumber(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (nums[mid] == mid) start = mid + 1;
            else end = mid - 1;
        }
        return start;
    }

    /**
     * 剑指 Offer 54. 二叉搜索树的第k大节点
     * 给定一棵二叉搜索树，请找出其中第k大的节点。
     *
     * 示例 1:
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 4
     *
     * 示例 2:
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 4
     *
     * TODO 中序遍历所得到的序列，就是有序的。
     * 中序遍历二叉搜索树，遍历的同时，把遍历到的节点存到一个可变数组里（Java的话，可以用ArrayList)。
     */
    /**
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public int kthLargest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(root, list);
        return list.get(list.size() - k);
    }

    public void dfs(TreeNode root, List<Integer> list) {
        if (root == null) return;
        if (root.left != null) dfs(root.left, list);
        list.add(root.val);
        if (root.right != null) dfs(root.right, list);
    }

    /**
     * 剑指 Offer 55 - I. 二叉树的深度
     * 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
     * <p>
     * 例如：
     * 给定二叉树 [3,9,20,null,null,15,7]，
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回它的最大深度 3 。
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    /**
     * 剑指 Offer 55 - II. 平衡二叉树
     * 输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
     * <p>
     * 示例 1:
     * 给定二叉树 [3,9,20,null,null,15,7]
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 返回 true 。
     * <p>
     * 示例 2:
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     * <p>
     * 1
     * / \
     * 2   2
     * / \
     * 3   3
     * / \
     * 4   4
     * 返回 false 。
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1) {
            return isBalanced(root.left) && isBalanced(root.right);
        }
        return false;
    }

    /**
     * 剑指 Offer 56 - I. 数组中数字出现的次数
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
     * <p>
     * 示例 1：
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     * <p>
     * 示例 2：
     * 输入：nums = [1,2,10,4,1,4,3,3]
     * 输出：[2,10] 或 [10,2]
     * <p>
     * TODO 异或运算的各种性质 并且学习了提交记录中排第一的优化方案，异或的运算方法是一个二进制运算，异或的规则是转换成二进制比较，相同为0，不同为1
     * <p>
     * 异或运算的几个性质
     * <p>
     * 交换律
     * 结合律（即(a^b)^c == a^(b^c)）
     * 对于任何数x，都有x^x=0，x^0=x
     * 自反性 A XOR B XOR B = A xor 0 = A ---> A XOR B = C 则 C XOR B = A
     */
    public static int[] singleNumbers(int[] nums) {
        int x = 0; // 用于记录 A 和 B 的 异或结果

        /** 得到A^B的结果
         基于异或运算的以下几个性质
         1. 交换律
         2. 结合律
         3. 对于任何数x，都有x^x=0，x^0=x
         */
        for (int val : nums) {
            // 数组中的数与0进行异或操作，得到该数的二进制数，由于x=0，所以可以得到 x = x^（val1）^(val2)^(val3)^(val4)........
            // TODO a1^b 运算方式：a1 - b 将结果转换成二进制
            // 两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。
            //
            // 比如：8^11.
            // 8转为二进制是1000，11转为二进制是1011.从高位开始比较得到的是：0011.然后二进制转为十进制，就是Integer.parseInt("0011",2)=3;
            // TODO 这里的 x = A ^ B  (两个不重复数的异或)
            x ^= val;
            // System.out.println(Integer.toBinaryString(x));
        }
        // x & (-x)本身的作用是得到最低位的1，
        // 两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
        //
        // 比如：129 & 128.
        // 129转换成二进制就是10000001，128转换成二进制就是10000000。从高位开始比较得到，得到10000000，即128.
        // 得到最后一个不重复数二进制异或结果，根据二进制为1的位置来找到第二个不唯一数的异或比较
        int flag = x & (-x);
        // 而我们所需要的做到的是：利用这个1来进行分组，也就是做到将A和B区分开
        // 前面已经知道，x是我们需要的结果数A和B相异或的结果，也就是说，x的二进制串上的任何一个1，都能成为区分A和B的条件
        // 因此我们只需要得到x上的任意一个1，就可以做到将A和B区分开来
        // x&(-x)：保留二进制下最后出现的1的位置，其余位置置0（即一个数中最大的2的n次幂的因数
        // x&(x-1)：消除二进制下最后出现1的位置，其余保持不变
        // TODO res 用来存放第二个不重复出现结果
        int res = 0; // 用于记录A或B其中一者

        // 分组操作
        for (int val : nums) {
            // 根据二进制位上的那个“1”进行分组
            // 需要注意的是，分组的结果必然是相同的数在相同的组，且还有一个结果数
            // 因此每组的数再与res=0一路异或下去，最终会得到那个结果数A或B
            // 且由于异或运算具有自反性，因此只需得到其中一个数即可
            if ((flag & val) != 0) {
                res ^= val;
            }
        }
        // 利用先前的x进行异或运算得到另一个，即利用自反性
        return new int[]{res, x ^ res};
    }

    public static int[] singleNumbers2(int[] nums) {
        int AB = 0;
        for (int num : nums) {
            AB ^= num;
        }
        int lastB = AB & (-AB);
        int B = 0;
        for (int num : nums) {
            if ((lastB & num) != 0) {
                B ^= num;
            }
        }
        return new int[]{B, AB ^ B};
    }

    /**
     * 剑指 Offer 56 - II. 数组中数字出现的次数 II
     * <p>
     * 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
     * <p>
     * 示例 1：
     * 输入：nums = [3,4,3,3]
     * 输出：4
     * <p>
     * 示例 2：
     * 输入：nums = [9,1,7,9,7,9,7]
     * 输出：1
     * <p>
     * TODO ~ 运算规则：如果位为0，结果是1，如果位为1，结果是0.
     * <<	num<< n	相当于 num×2n，算数左移（逻辑左移）
     * >>	num>>n	相当于 num/2n，算数右移
     * >>>	num>>>n	逻辑右移，当num为正数和算术右移一个效果
     * &：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
     * ｜:同为０时为０，否则为１
     * <p>
     * 解题思路：
     * 如下图所示，考虑数字的二进制形式，对于出现三次的数字，各二进制位出现的次数都是 3 的倍数。
     * 因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。
     */
    public int singleNumber(int[] nums) {
        // 数组求和取余
        Set<Long> s = new HashSet<>();
        long rs = 0;
        for (long i : nums) {
            // 判断set中是否存在 i
            if (!s.contains(i)) {
                s.add(i);
                rs += i << 1;//加的时候加双倍
            } else {
                rs -= i;//减的时候减单倍
            }
        }
        return (int) (rs / 2);
    }

    public int singleNumber1(int[] nums) {//本算法同样适用于数组nums中存在负数的情况
        //输入数组长度不符合要求，返回-1;
        if (nums.length == 0) return -1;
        //辅助数组：java int类型有32位，其中首位为符号位
        int[] bitSum = new int[32];
        int res = 0;
        for (int num : nums) {
            int bitMask = 1;//需要在这里初始化，不能和res一起初始化
            for (int i = 31; i >= 0; i--) {//bitSum[0]为符号位
                // 这里同样可以通过num的无符号右移>>>来实现，否则带符号右移(>>)左侧会补符号位，对于负数会出错。
                // 但是不推荐这样做，最好不要修改原数组nums的数据
                // &：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
                if ((num & bitMask) != 0) bitSum[i]++;//这里判断条件也可以写为(num&bitMask)==bitMask,而不是==1
                bitMask = bitMask << 1;//左移没有无符号、带符号的区别，都是在右侧补0
            }
        }
        for (int i = 0; i < 32; i++) {//这种做法使得本算法同样适用于负数的情况
            res = res << 1;
            res += bitSum[i] % 3;//这两步顺序不能变，否则最后一步会多左移一次
        }
        return res;
    }

    public static int singleNumber3(int[] nums) {
        int[] counts = new int[32];
        for (int num : nums) {
            for (int j = 0; j < 32; j++) {
                // counts[j] += num & 1;
                // 末尾一位 1 的个数相加
                counts[j] = counts[j] + num & 1;
                // 移动一位，继续求1出现的次数
                num = num >>> 1;
            }
        }
        // 需要从右往左进行逐个遍历
        int res = 0, m = 3;
        for (int i = 0; i < 32; i++) {
            // res = res * 2的n次
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }

    public static int singleNumber4(int[] nums) {
        int[] res = new int[32];
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                res[i] += num & 1;
                num = num >>> 1;
            }
        }
        int result = 0;
        int m = 3;
        for (int j = 0; j < 32; j++) {
            result <<= 1;
            result |= res[31 - j] % m;
        }
        return result;
    }

    /**
     * 剑指 Offer 57. 和为s的两个数字
     * <p>
     * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
     * <p>
     * 示例 1：
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[2,7] 或者 [7,2]
     * <p>
     * 示例 2：
     * 输入：nums = [10,26,30,31,47,60], target = 40
     * 输出：[10,30] 或者 [30,10]
     * <p>
     * TODO 思路：采用双指针来进行遍历数组
     */
    public int[] twoSum(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        while (start < end) {
            int sum = nums[start] + nums[end];
            if (sum > target) end--;
            else if (sum < target) start++;
            else return new int[]{nums[start], nums[end]};
        }
        return null;
    }

    /**
     * 剑指 Offer 57 - II. 和为s的连续正数序列
     * <p>
     * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
     * 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
     * <p>
     * 示例 1：
     * 输入：target = 9
     * 输出：[[2,3,4],[4,5]]
     * <p>
     * 示例 2：
     * 输入：target = 15
     * 输出：[[1,2,3,4,5],[4,5,6],[7,8]]
     */
    public static int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int mid = target / 2 + 1;
        for (int i = 1; i <= mid; i++) {
            int sum = i;
            for (int j = i + 1; j <= mid; j++) {
                sum += j;
                if (sum == target) {
                    // 数组长度 j - i + 1
                    int left = i;
                    int len = j - i + 1;
                    int[] res = new int[len];
                    for (int k = 0; k < len; k++) {
                        res[k] = left;
                        left++;
                    }
                    list.add(res);
                    break;
                }
                if (sum > target) {
                    break;
                }
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    /**
     * 剑指 Offer 58 - I. 翻转单词顺序
     * 输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
     * <p>
     * 示例 1：
     * 输入: "the sky is blue"
     * 输出: "blue is sky the"
     * <p>
     * 示例 2：
     * 输入: "  hello world!  "
     * 输出: "world! hello"
     * 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
     * <p>
     * 示例 3：
     * 输入: "a good   example"
     * 输出: "example good a"
     * 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     */
    public static String reverseWords(String s) {

        StringBuffer stringBuilder = new StringBuffer();
        String[] strings = s.trim().split(" ");
        for (int i = strings.length - 1; i >= 0; i--) {
            if (strings[i].equals("")) {
                continue;
            }
            // 到了结尾
            if (i == 0) {
                stringBuilder.append(strings[i].trim());
            } else {
                stringBuilder.append(strings[i].trim()).append(" ");
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 剑指 Offer 58 - II. 左旋转字符串
     * 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
     * 请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
     * <p>
     * 示例 1：
     * 输入: s = "abcdefg", k = 2
     * 输出: "cdefgab"
     * <p>
     * 示例 2：
     * 输入: s = "lrloseumgh", k = 6
     * 输出: "umghlrlose"
     */
    public String reverseLeftWords(String s, int n) {

        return s.substring(n, s.length()) + s.substring(0, n);
    }

    /**
     * 剑指 Offer 59 - I. 滑动窗口的最大值
     * <p>
     * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
     * <p>
     * 示例:
     * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
     * 输出: [3,3,5,5,6,7]
     * <p>
     * 解释:
     * <p>
     * 滑动窗口的位置                最大值
     * ---------------               -----
     * [1  3  -1] -3  5  3  6  7       3
     * 1 [3  -1  -3] 5  3  6  7       3
     * 1  3 [-1  -3  5] 3  6  7       5
     * 1  3  -1 [-3  5  3] 6  7       5
     * 1  3  -1  -3 [5  3  6] 7       6
     * 1  3  -1  -3  5 [3  6  7]      7
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || k == 0 || k == 1) return nums;
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            int len = i + k - 1;
            if (len <= nums.length - 1) {
                int max = 0;
                for (int a = i; a <= len; a++) {
                    max = Math.max(nums[a], max);
                }
                list.add(max);
            } else {
                break;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    /**
     * 剑指 Offer 59 - II. 队列的最大值
     * <p>
     * 请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
     * <p>
     * 若队列为空，pop_front 和 max_value 需要返回 -1
     * <p>
     * 示例 1：
     * <p>
     * 输入:
     * ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
     * [[],[1],[2],[],[],[]]
     * 输出: [null,null,null,2,1,2]
     * 示例 2：
     * <p>
     * 输入:
     * ["MaxQueue","pop_front","max_value"]
     * [[],[],[]]
     * 输出: [null,-1,-1]
     */
    class MaxQueue {
        Queue<Integer> queue;
        // Deque 双端队列(两端都可进出)
        Deque<Integer> maxQueue;

        public MaxQueue() {
            queue = new LinkedList<Integer>();
            maxQueue = new LinkedList<Integer>();
        }

        // 得到最大值
        public int max_value() {
            if (maxQueue.isEmpty()) return -1;
            else return maxQueue.peek();
        }

        public void push_back(int value) {
            queue.offer(value);
            while (!maxQueue.isEmpty() && value > maxQueue.peekLast())
                maxQueue.pollLast();
            maxQueue.offer(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            int val = queue.poll();
            if (maxQueue.peek() == val) {
                maxQueue.pop();
            }
            return val;
        }
    }

    /**
     * 剑指 Offer 61. 扑克牌中的顺子
     * <p>
     * 从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。
     * <p>
     * 示例 1:
     * 输入: [1,2,3,4,5]
     * 输出: True
     * <p>
     * 示例 2:
     * 输入: [0,0,1,2,5]
     * 输出: True
     * <p>
     * TODO 思路：
     * 此 55 张牌是顺子的 充分条件 如下：
     * <p>
     * 除大小王外，所有牌 无重复 ；
     * 设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：
     * max - min < 5
     * max−min<5
     */
    public boolean isStraight(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int max = 0;
        int min = 0;
        for (int num : nums) {
            if (num == 0) continue;
            max = Math.max(num, max);
            min = Math.min(num, min);
            if (set.contains(num)) return false;
            set.add(num);
        }
        return max - min < 5;
    }

    /**
     * 剑指 Offer 62. 圆圈中最后剩下的数字
     * <p>
     * 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
     * <p>
     * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
     * <p>
     * 示例 1：
     * 输入: n = 5, m = 3
     * 输出: 3
     * <p>
     * 示例 2：
     * 输入: n = 10, m = 17
     * 输出: 2
     */
    public static int lastRemaining(int n, int m) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            arrayList.add(i);
        }
        int start = 0;
        while (n > 1) {
            // 起始位置加上第 m - 1 个，得到要删除的索引位置
            // TODO %n 这里要注意
            start = (start + m - 1) % n;
            arrayList.remove(start);
            n--;
        }
        return arrayList.get(0);
    }

    /**
     * 剑指 Offer 63. 股票的最大利润
     * <p>
     * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
     * <p>
     * 示例 1:
     * 输入: [7,1,5,3,6,4]
     * 输出: 5
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     * 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
     * <p>
     * 示例 2:
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        int profit = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (min >= prices[i]) {
                min = prices[i];
            } else {
                profit = Math.max(profit, prices[i] - min);
            }
        }
        return profit;
    }

    /**
     * 剑指 Offer 64. 求1+2+…+n
     * <p>
     * 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     * <p>
     * 示例 1：
     * 输入: n = 3
     * 输出: 6
     * <p>
     * 示例 2：
     * 输入: n = 9
     * 输出: 45
     */
    public int sumNums(int n) {

        int sum = n;
        boolean flag = n > 0 && (sum += sumNums(n - 1)) > 0;
        return sum;
    }

    /**
     * 剑指 Offer 65. 不用加减乘除做加法
     * <p>
     * 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
     * <p>
     * 示例:
     * 输入: a = 1, b = 1
     * 输出: 2
     * <p>
     * TODO
     * 异或运算：x^x=0，x^0=x
     * &：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
     */
    public int add(int a, int b) {
        // 根据二进制计算
        while (b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位,二进制左移一位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }

    /**
     * 剑指 Offer 66. 构建乘积数组
     * <p>
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
     * 解释：意思是b[i]的值是数组a中除了下标i以外的元素的积
     * <p>
     * 示例:
     * 输入: [1,2,3,4,5]
     * 输出: [120,60,40,30,24]
     */
    public int[] constructArr(int[] a) {

        int len = a.length;
        int[] res = new int[len];
        // 从左往右
        for (int i = 0; i < len; i++) {
            int sum = 1;
            for (int j = i + 1; j < len; j++) {
                sum *= a[j];
            }
            res[i] = sum;
        }
        // 从右往左
        for (int i = len - 1; i >= 0; i--) {
            int sum = 1;
            for (int j = i - 1; j >= 0; j--) {
                sum *= a[j];
            }
            res[i] *= sum;
        }

        return res;
    }

    public int[] constructArr1(int[] a) {

        int len = a.length;
        int[] res = new int[len];
        // 乘以左侧数
        int sum = 1;
        for (int i = 0; i < len; i++) {
            res[i] = sum;
            sum *= a[i];
        }
        // 乘以右侧数
        int cur = 1;
        for (int i = len - 1; i >= 0; i--) {
            res[i] *= cur;
            cur *= a[i];
        }
        return res;
    }

    /**
     * 剑指 Offer 67. 把字符串转换成整数
     * <p>
     * 写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
     * <p>
     * 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
     * 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；
     * 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
     * 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
     * <p>
     * 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
     * <p>
     * 在任何情况下，若函数不能进行有效的转换时，请返回 0。
     * <p>
     * 说明：
     * 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。
     * <p>
     * 示例 1:
     * 输入: "42"
     * 输出: 42
     * <p>
     * 示例 2:
     * 输入: "   -42"
     * 输出: -42
     * 解释: 第一个非空白字符为 '-', 它是一个负号。
     *      我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
     * <p>
     * 示例 3:
     * 输入: "4193 with words"
     * 输出: 4193
     * 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
     * <p>
     * 示例 4:
     * 输入: "words and 987"
     * 输出: 0
     * 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     * 因此无法执行有效的转换。
     * <p>
     * 示例 5:
     * 输入: "-91283472332"
     * 输出: -2147483648
     * 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
     *      因此返回 INT_MIN (−231) 。
     *  
     */
    public int strToInt(String str) {
        // 去除字符串空格
        String string = str.trim();
        if (string.length() == 0) return 0;
        // 判断首位了
        // 首位合格的无非就'+'或'-'或数字三种情况，其他的一概滚蛋
        // '+''-'肯定是要把它去掉的，这样三种情况就统一了
        // '-abc'这种有可能
        // 既然要去掉正负号，那肯定要出个boolean记一下是不是负数
        char[] chars = string.toCharArray();
        boolean bool = false;
        // 判断首位,Character.isDigit(chars[0])判断是否为数字
        if (chars[0] == '+' || chars[0] == '-' || Character.isDigit(chars[0])) {
            // 判断首位符号
            if (chars[0] == '+' || chars[0] == '-') {
                if (chars[0] == '-') {
                    bool = true;
                }
                // 去除 + - 字符串，复制数组
                chars = Arrays.copyOfRange(chars, 1, chars.length);
            }
            int index = 0;
            long intStr = 0;
            while (index < chars.length && Character.isDigit(chars[index])) {
                // char 类型转换为int时，只需要 - '0'
                intStr *= 10;
                intStr += chars[index] - '0';
                if (intStr > Integer.MAX_VALUE) {
                    //正负号看是正数负数，返回最大值
                    return bool ? Integer.MIN_VALUE : Integer.MAX_VALUE;
                }
                index++;
            }
            return bool ? -(int) intStr : (int) intStr;
        }

        // 首位不满足条件
        return 0;
    }

    /**
     * 面试题60. n个骰子的点数
     * <p>
     * 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
     * <p>
     * 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
     * <p>
     * 示例 1:
     * 输入: 1
     * 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
     * <p>
     * 示例 2:
     * 输入: 2
     * 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]
     * <p>
     * 限制：
     * 1 <= n <= 11
     * <p>
     * TODO 动态规划问题
     */
    public double[] dicesProbability(int n) {
        if (n == 0) return null;
        double pre[] = {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
        for (int i = 2; i <= n; i++) {
            // 定义返回数组
            double[] doubles = new double[5 * i + 1];
            // 遍历初始数组
            for (int j = 0; j < pre.length; j++) {
                // 六个面
                for (int k = 0; k < 6; k++) {
                    doubles[j + k] += pre[j] / 6;
                }
            }
            pre = doubles;
        }
        return pre;
    }

    /**
     * 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
     * <p>
     * <p>
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * <p>
     * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
     * <p>
     * 示例 1:
     * <p>
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     * 输出: 6
     * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
     * 示例 2:
     * <p>
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     * 输出: 2
     * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        if (root == null)
            return null;
        if (root.val > p.val && root.val > q.val)
            // 在左子树中
            return lowestCommonAncestor(root.left, p, q);
        if (root.val < p.val && root.val < q.val)
            // 在右子树中
            return lowestCommonAncestor(root.right, p, q);
        return root;
    }

    /**
     * 剑指 Offer 68 - II. 二叉树的最近公共祖先
     * <p>
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * <p>
     * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
     * <p>
     * 示例 1:
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
     * 输出: 3
     * 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
     * <p>
     * 示例 2:
     * 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
     * 输出: 5
     * 解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     * <p>
     * TODO 思路：
     * 三种情况：
     * 1、p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
     * 2、p q 都在左子树
     * 3、p q 都在右子树
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            // p q 一个在左，一个在右
            return root;
        }
        if (left != null) {
            // p q 都在左子树
            return left;
        }
        if (right != null) {
            // p q 都在右子树
            return right;
        }
        return null;
    }


    public static void main(String[] args) throws Exception {

//        int[][] matrix = {{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
//        int[][] matrix2 = {{1,2,3},{4,5,6},{7,8,9}};
//        int[] res = spiralOrder(matrix);
//
//        MinStack minStack = new MinStack();
//        minStack.push(-2);
//        minStack.push(0);
//        minStack.push(-3);
//        minStack.min();   //--> 返回 -3.
//        minStack.pop();
//        minStack.top();   //--> 返回 0.
//        minStack.min();   //--> 返回 -2.

//        List<List<Integer>> res = new ArrayList<>();
        // permutation("abc");
//        int a = lengthOfLongestSubstring("abcabcbb");
//        int[] ints = {9,1,7,9,7,9,7};
//        int[] a = {1,3,-1,-3,5,3,6,7};
//        int sum = reversePairs(ints);
//        int count = reversePairs2(ints);
//        int[] res = singleNumbers(a);
//        int c = 2 ^ 10;
//        System.out.println(Integer.toBinaryString(c));
//        int a1=15;
//        int b=4;
//        System.out.println("a 与 b 异或的结果是："+(a1^b));
//        System.out.println(Integer.toBinaryString(a1^b));
        //int s = singleNumber3(ints);
//        int[][] as = findContinuousSequence(9);
//        int[] a = {1,3,-1,-3,5,3,6,7};
//        maxSlidingWindow(a,3);

//        System.out.println(1&1);

        lastRemaining(5, 3);
        System.out.println("=============");
    }


}
